#!/usr/bin/env python
# -*- coding:utf-8 -*-

# file:analyzer.py
# author:邹煜扬
# datetime:2024/12/18 15:16
# software: PyCharm
"""
this is function  description 
"""

from .grammar import Grammar
from .itemset import ItemSet
from .item import Item
from .production import Production


# import module your need

class Analyzer:
    def __init__(self, grammar):
        self.grammar = grammar
        #对文法进行扩展
        self.grammar.expand_grammar()
        self.all_symbols = self.grammar.get_all_symbols()
        self.states = []
        self.transitions_table=[]
        self.transitions = {}
        self.compute_closure_goto()

    def compute_closure_goto(self):
        '''
        计算LR(0)项集规范族中所有状态的闭包和转移函数
        :return:
        '''

        # 初始化初始项目和初始状态
        initial_item = Item(Production(self.grammar.S+"'", self.grammar.S),0)
        initial_state = ItemSet(None,self.grammar)
        initial_state.add_item(initial_item)
        initial_state=initial_state.closure()
        # 将初始状态添加到状态集合中
        self.states.append(initial_state)

        # 使用队列实现广度优先搜索，初始状态入队
        queue = [initial_state]

        # 循环直到队列为空
        while queue:
            # 出队当前状态
            current_state = ItemSet(None,self.grammar)
            queue_pop_state=queue.pop(0)
            for item in queue_pop_state:
                current_state.add_item(item)

            #求出当前状态中‘.’后面的符号
            after_dot_symbols = current_state.after_dot_symbols()


            # 对每个'.'后面的符号进行遍历，把产生出的新项目集加入状态列表并入队
            for symbol in after_dot_symbols:
                # 计算当前状态通过符号symbol转移后的新状态的核
                next_nucleus = current_state.next_nucleus(symbol)
                #如果闭包非空且不在已有状态集合中
                if next_nucleus is not None:#下一个状态不为空
                    new_nucleus = next_nucleus.closure()#求下一个状态的闭包
                    if not self.is_nucleus_in_states(new_nucleus):#闭包不在已有状态集中，加入状态集，入队
                        self.states.append(new_nucleus)
                        queue.append(new_nucleus)
                    # 记录转移函数
                    self.transitions[(current_state, symbol)] = new_nucleus

    def is_nucleus_in_states(self, nucleus):
        for state in self.states:
            # 如果核的的长度和一个状态的长度相同，则比较它们的项集,长度不同则说明这个状态和核不是同一个状态
            if len(state) == len(nucleus):
                if self.is_same(state, nucleus):
                    return True

        return False  # 没有找到完全匹配的状态

    def is_same(self, state1, state2):
        all_items_find = True
        for item1 in state1:
            this_item_find=False
            for item2 in state2:
                if item1==item2:
                    this_item_find=True
                    break
            if not this_item_find:
                all_items_find=False
                break
        return all_items_find

    def print_states(self):
        for i, state in enumerate(self.states):
            print(f"State {i}:")
            print(state)

    def print_transitions_table(self):
        VN_symbols = sorted(self.grammar.VN)
        VT_symbols = sorted(self.grammar.VT)
        # 添加特殊符号#
        VT_symbols.append('#')
        sorted_symbols = VT_symbols + VN_symbols
        # 初始化表格,行和列分别表示状态和符号
        self.transitions_table = [[''] * (len(self.states) + 10) for _ in range(len(sorted_symbols) + 10)]

        # 设置表头


        for row in range(len(self.states)):
            self.transitions_table[row + 1][0] = row#第一行放字符，所以row+1

        for col, symbol in enumerate(sorted_symbols, start=1):#第一列放状态，所以从1开始
            self.transitions_table[0][col] = symbol

        # 填充表格
        for row in range(1, len(self.states) + 1):
            for col in range(1, len(sorted_symbols) + 1):
                # 获取当前符号
                current_states = self.transitions_table[row][0]#只是一个索引
                current_symbol = self.transitions_table[0][col]

                # 如果是规约状态，则填写规约式的序号
                if self.is_reduce_state(self.states[current_states]):
                    production_index = self.get_reduce_production_index(self.states[current_states])

                    if production_index == 0:  # 增广产生式的索引为0
                        # 只有#列才标注acc
                        if current_symbol == '#':
                            cell_value = 'acc'
                        else:
                            cell_value = ''
                    else:  # 除了增广产生式以外的情况
                        if current_symbol in VT_symbols:  # 只填写终结符栏
                            cell_value = 'r' + str(production_index)
                        else:
                            cell_value = ''

                else:
                    # 计算goto
                    goto_state = self.goto(self.states[current_states], current_symbol)

                    # 如果存在goto状态，填写状态编号，并根据符号类型添加前缀
                    if goto_state:
                        # 查找goto_state在self.states中的索引
                        goto_index = self.states.index(goto_state)
                        cell_value = goto_index
                        if current_symbol in VT_symbols:#非终结符添上前缀S
                            cell_value = 'S' + str(cell_value)
                    else:
                        cell_value = ''

                # 将单元格值填写到表格中
                self.transitions_table[row][col] = cell_value

        #打印表格
        for row in range(len(self.states) + 1):
            for col in range(len(sorted_symbols) + 1):
                print(f"{self.transitions_table[row][col]:<10}", end='|')
            print()

    def is_reduce_state(self, state):
        for item in state:
            if item.dot_position < len(item.production.right):#有点不在项目的最后，说明还可以继续走下去，所以不是可归约状态
                return False
        return True

    def get_reduce_production_index(self, state):
        for production_index, production in enumerate(self.grammar.P):
            if state[0].production == production:
                return production_index

    def goto(self, state, symbol):
        for item in state:
            if item.dot_position < len(item.production.right) and item.production.right[item.dot_position] == symbol:
                new_item = Item(production=item.production, dot_position=item.dot_position + 1)
                new_state = ItemSet(None,self.grammar)
                new_state.add_item(new_item)
                return new_state.closure()
        return None

    def parse_string(self, input_string):
        '''            使用LR(0)分析表判断输入字符串是否属于文法
         :param input_string: 输入字符串
        :return: 如果是文法中的句子，返回True；否则，返回False
        '''
        # 将输入字符串添加结束符'#'
        input_string += '#'

        # 初始化分析栈，初始状态，和输入字符串索引
        states_stack = [0]#状态栈
        symbol_stack = ['#']#符号栈
        input_index = 0#相当于是输入串的栈顶指针

        step = 1  # 步骤计数
        goto_state = ''  # 初始化goto_state
        # 打印表头
        print(f"步骤  |         状态栈         |              符号栈              |      输入串       | ACTION | GOTO ")
        while True:

            # 获取当前状态和输入符号
            current_state = states_stack[-1]
            current_symbol = input_string[input_index]

            # 查找LR(0)分析表中的动作
            action = self.get_action(current_state, current_symbol)

            # 打印步骤信息
            print(f"{step:<4} |  {str(states_stack):<20} |  {str(symbol_stack):<30} | "
                  f" {input_string[input_index:]:<15} | "
                  f" {action:<5} | ", end="")

            # 如果动作为空，说明分析表中无对应的动作，字符串不属于文法
            if not action:
                return False

            # 根据动作类型进行处理
            if action.startswith('S'):
                # 移入动作
                next_state = int(action[1:])
                states_stack.append(next_state)
                symbol_stack += input_string[input_index]
                input_index += 1
                print()

            elif action.startswith('r'):
                # 规约动作
                production_index = int(action[1:])
                production = self.grammar.P[production_index]

                # 弹出产生式右部的符号
                for _ in range(len(production.right)):
                    states_stack.pop()
                    symbol_stack.pop()

                # 获取规约后的状态

                # #查找弹出产生式右部后的符号栈栈顶和产生式左部在状态转移表中对应的动作
                goto_state = self.get_action(states_stack[-1], production.left)
                #把goto栈的动作移入状态栈
                states_stack.append(goto_state)
                #把产生式左部移入符号栈
                symbol_stack.append(production.left)

                print(f" {goto_state}")

            elif action == 'acc':

                print()
                print("接受")
                # 接受动作，字符串属于文法
                return True

            step += 1  # 步骤计数加一

    def get_action(self, state, symbol):
        #查找输入串栈顶字符在状态转移表的第几列
        symbol_index= self.transitions_table[0].index(symbol)
        #查找状态栈顶状态在状态转移表第几行
        state_index = state+1
        return self.transitions_table[state_index][symbol_index]


